#include <cstdio>
/*
多重背包问题：
每个物品可取的数量为一个确定整数
对该整数进行拆分(拆分过程还没细看)
拆分后转换成0-1背包
*/
int max(int a, int b);
struct good_info {
    int weight;
    int value;
} data_info[2001];
int dp[101];

int main(int argc, char const* argv[])
{
    int case_num;
    scanf("%d", &case_num);
    for (int k = 0; k < case_num; k++) {
        int s, n;
        scanf("%d%d", &s, &n);
        int goods_count = 0;

        for (int i = 1; i <= n; i++) {
            int value, weight, num;
            scanf("%d%d%d", &weight, &value, &num);
            int c = 1;
            while (num - c > 0) {
                num -= c;
                data_info[++goods_count].weight = c * weight;
                data_info[goods_count].value = c * value;
                c *= 2;
            }
            data_info[++goods_count].weight = weight * num;
            data_info[goods_count].value = value * num;
        }
        for (int i = 1; i <= s; i++)
            dp[i] = 0;
        for (int i = 1; i <= goods_count; i++) {
            for (int j = s; j >= data_info[i].weight; j--)
                dp[j] = max(dp[j], dp[j - data_info[i].weight] + data_info[i].value);
        }
        printf("%d\n", dp[s]);
    }
    return 0;
}

int max(int a, int b) { return a > b ? a : b; }